package com.xsherl.leetcode.solution;

import java.util.Arrays;

/**
 * @Author: sherl
 * @Date: 2021/5/24 21:02
 */
public class LongestSubstring {

    public int longestSubstring(String s, int k) {
        return subLongest(s, k, 0, s.length());
    }

    public int subLongest(String s, int k, int x, int y) {
        if (y - x < k) {
            return 0;
        }
        int[] count = new int[26];
        for (int i = x; i < y; ++i) {
            count[s.charAt(i) - 'a']++;
        }
        int pre = x, max = 0;
        for (int i = x; i < y; ++i) {
            if (count[s.charAt(i) - 'a'] < k) {
                int c = subLongest(s, k, pre, i);
                pre = i + 1;
                if (c > max) {
                    max = c;
                }
            }
        }
        int c = pre == x ? y - x : subLongest(s, k, pre, y);
        if (c > max) {
            max = c;
        }
        return max;
    }

}
